#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <algorithm>
class Solution {
public:
    std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
        std::vector<std::vector<int>> vv;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size();)//̶a
        {
            int left = i + 1, right = nums.size() - 1, tag = -nums[i];
            while (left < right)
            {
                if (nums[i] > 0) break;
                int sum = nums[left] + nums[right];
                if (sum < tag) left++;
                else if (sum > tag) right--;
                else
                {
                    vv.push_back({ nums[i],nums[left],nums[right] });
                    left++;
                    //ȥ
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    right--;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                }
            }
            i++;
            while (i < nums.size() - 1 && nums[i] == nums[i - 1]) i++;
        }
        return vv;
    }
};
int main()
{
    std::vector<int> v({ -1,0,1,2,-1,-4 });
    std::vector<std::vector<int>> ret(Solution().threeSum(v));
    for (auto e : ret)
    {
        for (auto x : e)
        {
            std::cout << x << " ";
        }
        std::cout << std::endl;
    }
	return 0;
}
/*
题目链接:https://leetcode.cn/problems/3sum/description/
*/